package com.lz.sort;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
        System.out.println("Hello World");
        int[] a = {12, 20, 5, 16, 15, 1, 30, 45, 5, 23, 9};
        speed();
        method01(a, 0, a.length - 1);
        PrintUtil.printArray(a);
    }


    private static void speed() {
        int[] x = new int[10000];
        int[] y = new int[10000];
        int[] z = new int[10000];
        Random random = new Random();
        for (int j = 0; j < x.length; j++) {
            int i = random.nextInt(10000);
            x[j] = i;
            y[j] = i;
            z[j] = i;
        }

        System.out.println("--------------比较---------------------");

        int start = 0;
        int end = x.length - 1;
        long t1 = System.currentTimeMillis();
        quickSort(x, start, end);
        long t2 = System.currentTimeMillis();
        System.err.println("quick sort:" + (t2 - t1));
        BubbleSort.bubbleSort(y);
        long t3 = System.currentTimeMillis();
        System.err.println("mao pao:" + (t3 - t2));
        Arrays.sort(z);
        long t4 = System.currentTimeMillis();
        System.err.println("arrays : " + (t4 - t3));

    }

    public static void sort(int[] a, int low, int high) {
        int i = low;
        int j = high;
        int key = a[low];
        while (i < j) {
            // 从后往前比较{ 12, 20, 5, 16, 15, 1, 30, 45, 23, 9 };
            while (j > i && a[j] >= key) // 如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                j--;
            if (a[j] <= key) {
                int temp = a[j];//temp=9,key=12
                a[j] = a[i];//{ 9, 20, 5, 16, 15, 1, 30, 45, 23, 12 };
                a[i] = temp;
            }
            // 从前往后比较
            while (j > i && a[i] <= key)// 如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                i++;
            if (a[i] >= key) {
                int temp = a[i];//temp=20,key=12
                a[i] = a[j];
                a[j] = temp;// 基数key位置往后移动一位 { 9, 12, 5, 16, 15, 1, 30, 45, 23, 20 };
            }
            // 此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
        }
        // 递归,两端
        if (i > low)
            sort(a, low, i - 1);// 左边序列。第一个索引位置到关键值索引-1
        if (j < high)
            sort(a, j + 1, high);// 右边序列。从关键值索引+1到最后一个

    }


    public static void quickSort(int[] a, int low, int high) {
        int start = low;
        int end = high;
        int key = a[low];
        while (start < end) {
            while (start < end && a[end] >= key) end--;
            if (a[end] < key) {
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
            while (start < end && a[start] <= key) start++;
            if (a[start] > key) {
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
        }
        if (start > low) quickSort(a, low, start - 1);
        if (end < high) quickSort(a, end + 1, high);

    }

    /**
     *  交换 01三次赋值，02一次赋值
     * @param a
     * @param low
     * @param high
     */
    public static void quickSort02(int[] a, int low, int high) {
        int i = low;
        int j = high;
        int key = a[low];
        while (i < j) {
            while (i < j && a[j] >= key) j--;
            if (a[j] < key) {
                a[i] = a[j];

            }
            while (i < j && a[i] <= key) i++;
            if (a[i] > key) {
                a[j] = a[i];
            }

        }
        a[i] = key;
        if (i > low) quickSort02(a, low, i - 1);
        if (j < high) quickSort02(a, j + 1, high);

    }

    public static void method01(int[] a, int start, int end) {
        int i = start;
        int j = end;
        int p = a[start];
        while (i < j) {
            while (i < j && a[j] >= p) j--;
            if (a[j] < p) a[i] = a[j];
            while (i < j && a[i] <= p) i++;
            if (a[i] > p) a[j] = a[i];

        }
        a[i] = p;
        if (i > start) method01(a, start, i - 1);
        if (j < end) method01(a, j + 1, end);
    }

}
